Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string of characters. Hashing is used to index and retrieve items in a database because it is faster to locate the items from the database by means of the shorter length of the hash key than by using the original string to locate the item in the database. The above process of retrieving items by means of the shorter length hashed key is referred to herein as the “hash function.”
Hashing is also used to encrypt and decrypt digital signatures which are used to authenticate message senders and receivers. The digital signature is transformed by means of the hash function into a hashed value, also referred to as “message digest.” The digital signature and the message digest are then transmitted from the sender to a receiver. The receiver then derives the message digest from the transmitted digital signature by applying the same hash function as that applied by the sender. The receiver then compares the derived message digest and the message digest transmitted by the sender to the receiver. If there is no alteration in the digital signal during transmission or in the message digest during transmission, the comparison operation at the receiver should result in the same message digest as the one transmitted from the sender to the receiver.
Skein is a family of hash functions based on a tweakable block cipher. The term “block cipher” herein refers to applying an encryption algorithm on blocks of data message to generate encrypted data. The term “tweakable” herein refers to the ability to randomize the output (i.e., encrypted data) of the block cipher. One such tweakable block cipher is called “Threefish.” The process or rule of computing the hashed output from the Threefish is referred as the “mode.” One known mode is the Unique Block Iteration (UBI) mode.
In 2005 X. Wang and her colleagues (Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, “Finding Collisions in the Full SHA-1”, Crypto 2006, pp 19-36.) discovered that the standard hash algorithm SHA-1 admitted collisions at a cost of 262 SHA-1 operations instead of the expected value of 280. This result made a profound impression on the international cryptographic community, with the conclusion that SHA-1 was no longer usable for many of its basic functions. Due to the structural similarities between SHA-1 and the SHA-2 family, the integrity of the latter was immediately called into question. In response, the U.S. National Institute of Science and Technology (NIST) instituted an international competition to design a new cryptographic hashing algorithm to replace SHA-1 and SHA-2.
Previous hardware based implementations of UBI based Threefish block cipher Skein algorithm in a software platform on a general purpose microprocessor resulted in poor performance. The term “performance” herein refers to power consumption, silicon area, and processor clock cycles per byte to compute the hashed output. Even hardware based implementations of the UBI based Threefish Skein algorithm using standard cells and Field-programmable Gate Arrays (FPGAs) in a 0.18 μm CMOS process technology resulted in poor performance e.g., 1.88 Gbit/s throughput to compute a hashed output for Skein-256 hardware implementation operating a clock frequency of 73.52 MHz. A poor performing hardware implementation of UBI based Threefish block cipher Skein algorithm is an impediment to large scale secure commercial transactions that require secure digital finger prints i.e., hashed output.